% Chapter Template

\chapter{Introduction} % Main chapter title

\label{Chapter1} % Change X to a consecutive number; for referencing this chapter elsewhere, use \ref{ChapterX}

\lhead{Chapitre 1. \emph{Introduction}} % Change X to a consecutive number; this is for the header on each page - perhaps a shortened title

%----------------------------------------------------------------------------------------
%	SECTION 1
%----------------------------------------------------------------------------------------

%\section{Introduction}
	
	
%	Le problème de satisfaction de contrainte sont de plus en plus utilisé pour résoudre les problèmes combinatoires tel que l'ordonnancement,... \textbf{Continue}
%	
%	There are more and more applications in artificial intelligence that use constraint networks (CNs) to solve combinatorial problems, ranging from design to diagnosis, resource allocation to car sequencing, natural language understanding to machine vision. Finding a solution in	a constraint network involves looking for a set of value assignments, one for each variable, so that all the constraints are simultaneously satisfied. This task is NP-hard and many exponential time algorithms have been proposed to solve this problem. These algorithms, which make a systematic exploration of the search space, all have backtracking as a basis. As long as the unassigned variables have values consistent with the partial instantiation, they extend it by assigning values to variables. Otherwise, a dead-end is reached and some previous assignments have to be changed before going on with the partial instantiation extension. The explicit constraints of the network together induce some implicit constraints. Since basic search algorithms do not record these implicit	constraints, they waste time by repeatedly detecting the local inconsistencies caused by them. Filtering techniques are essential to reduce the size of the search space and so to improve the efficiency of search algorithms. They can be used during a preprocessing step to remove once and for all some local inconsistencies that otherwise would have been repeatedly found during search. They can also be maintained during search.
	
	% Background
	% - Une constraintes?
	% - Un CSP?
	% - Search
	% - Propagation
%	
%	L'exécution d'un programme dans la programmation par contrainte est basée sur la propagation et la recherche. La propagation vise à enlever les valeurs impossibles dans le domaines des variables, par l'examen de leur cohérence avec la contrainte. Ces dernières années, plusieurs notions de consistance plus forte que la consistance de domaine ont été proposées. L'objectif de ce mémoire est d'étudier les niveaux de consistance forts existants pour les contraintes binaires et les contraintes non-binaires. 
%	
%	Algorithmes de propagation pour les différentes consistances fortes associés à contrainte non binaire ont été étudiés et mis en œuvre dans le solveur AbsCon. Plus particulièrement, nous avons implémenté des algorithmes pour MaxRPWC, rPIC et RPWC. Nous avons développé des critères pour analyser les avantages de l'utilisation des consistances plus fortes. Les résultats expérimentaux montrent que ces consistances sont efficaces dans certaines classes de problèmes car ils peuvent élaguer plus que la consistance de domaine.

% dans la planification des activités d'une entreprise, les variables de décision pourraient être les heures de début et la durée des activités et les ressources nécessaires pour les exécuter, et la contrainte peut-être sur la disponibilité des ressources et sur ​​leur utilisation pour un nombre limité d'activités à un moment.

%  Constraint programming is a powerful paradigm for solving combinatorial search problems that draws on a wide range of techniques from artificial intelligence, computer science, databases, programming language, and operations research. Constraint programming is currently applied with success to many domains, such as scheduling, planing, vehicle routing, configuration, networks, and bioinformatics. The basic idea in constraint programming is that the user states the constraints and a general purpose constraint solver is used to solve them. Constraint a just relations, and a constraint satisfaction problem states which relations should hold among the given decision variables. For example, in scheduling activities in a company, the decision variables might be the starting times and the durations of activities and the resources needed to perform them, and the constraint might be on the availability of the resources and on their use for a limited number of activities at a time.

%  Constraint solvers take a read world problem like this, represented in terms of decision variables and constraints, and find an assignment to all the variables that satisfies the constraints. Constraint solvers search the solution space either systematically, as with backtracking or branch and bound algorithms, or use forms of local search which may be incomplete. The search space is a tree since  different values can be chosen for the different variables. The size of the search tree is exponential. It is therefore essential to reduce the size of the search tree and to detect inconsistency (or failure) of partial solutions as soon as possible. Such method is called propagation.  
  
%  The constraint programming framework combines propagation and search. The objective of propagation is to reduce the search space without removing solutions of the CSP. Propagation also detects early failure, and thus terminates branches of the search tree, saving fruitless  exploration of the search tree. Different levels of pruning can be achieved. These are usually  specified by a consistency property satisfied by the CSP after the propagation.
    
%  Domain consistency is the standard consistency property achieved by a propagation algorithm. The constraints are here considered individually; a constraint is domain consistent if all the values of each of its variables participates in a solution of this constraint. It is clear that the values that do not participate in a solution of the constraint can be pruned. When a propagation algorithm prunes a domain to achieve domain consistency, the resulting CSP is easier to solve. But achieving domain consistency has a cost. Weaker consistencies have been defined, such as forward checking or bound consistency. They prune less values than domain consistency,  but the propagation step is faster. Stronger consistencies have also been defined. Although  they require more computation, their pruning power is especially adapted for complex combinatorial problems such as those appearing in real life and industrial problems.

%  In theory, we study existing stronger consistency levels for both binary constraints and non-binary constraints which reduce the domain of variables. For binary constraint, we study the different consistencies such as: Restricted Path Consistency (RPC), Path Inverse Consistency (PIC), Max Restricted Path consistency (MaxRPC), Neighborhood Inverse   Consistency (NIC), Singleton Domain Consistency (SDC). These consistencies will be extended for the non binary constraints.  PIC have been extended into rPIC, RPC into RPWC and MaxRPC to maxRPWC. In \cite{stergiou2008strong}, NIC is extended into rNIC.

%  The rest of the thesis is structured as follows. Chapter 2 provides necessary background and definitions. In chapter 3, we study different consistencies for binary and non binary constraint. In chapter 4, algorithms for achieving stronger consistencies in non binary constraint will be presented. In chapter 5, we present the structure of solver AbsCon et implementation of these algorithms. Chapter 6 gives experimental results. Finally, we conclude and point to future work.

%  In practice, algorithms of propagation for different consistencies associated with non-binary constraint have been studied and implemented in the AbsCon solver. More particularly, we implemented	algorithms for MaxRPWC, rPIC and RPWC. We developed benchmarks to analyze the benefits of using stronger consistencies. Experimental results show that in some classes of problems these consistencies are efficient since they can prune more than domain consistency.
  

  La programmation par contraintes est un paradigme puissant pour résoudre des problèmes combinatoires qui s'appuient sur un large éventail de techniques de l'intelligence artificielle et de la recherche opérationnelle. La programmation par contraintes est actuellement appliquée avec succès à de nombreux domaines, tels que la planification, le routage de véhicule, la configuration, les réseaux, et la bio-informatique \cite{rossi2006handbook}.

  L'idée de base en programmation par contraintes est que l'utilisateur indique les contraintes, le problème et un solveur de contrainte qui est utilisé pour les résoudre.  La contrainte est une relations entre les variables, un problème de satisfaction de contraintes (un CSP) spécifie quelles relations doivent tenir entre les variable de décision données. Par exemple, dans la planification des activités d'une entreprise, les variables de décision peuvent être les heures de début et les contraintes peuvent être sur la disponibilité des ressources et sur leur utilisation pour un nombre limité d'activités à un moment.
  
  Un solveur de contrainte prend un problème, ce problème est représenté en terme de variables de décision et de contraintes et s'emploie à trouver une assignation à toutes les variables tout en satisfaisant les contraintes. Le solveur de contraintes cherche la solution dans l'espace de recherche soit systématiquement, comme avec retour en arrière (backtracking)
%  , ou soit en forme de recherche locale qui peut être incomplète
  . L'espace de recherche est un arbre car les valeurs différentes peuvent être choisies pour les différentes variables. La taille de l'arbre de recherche est exponentielle. Il est donc nécessaire de réduire la taille de l'arbre de recherche et de détecter les inconsistances (ou l'échec) des solutions partielles dès que possible. Cette méthode est appelée propagation.

  Le framework de programmation par contraintes combine la propagation et la recherche. L'objectif de la propagation est de réduire la taille de l'espace de recherche sans enlever la solution du problème. La propagation détecte également les échecs, et termine les branches de l'arbre de recherche, économise l'exploration inutile de l'espace de recherche. Différents niveaux d'élagage peuvent être atteints. Ceux-ci sont généralement définies par une propriété de consistance satisfaite par le CSP après la propagation.
  
  La consistance de domaine est la consistance standard atteinte par un algorithme de propagation. Les contraintes sont considérées individuellement, une contrainte est domaine consistant si toutes les valeurs de chacune de ses variables participent à une solution de cette contrainte. Les valeur qui ne satisfont pas cette propriété sont enlevées. Quand un algorithme de propagation pour la consistance de domaine est appliqué, le CSP résultant est plus facile à résoudre. Cependant, atteindre la consistance de domaine a un coût. Les consistances plus faibles ont été définies tels que \textit{forward checking} ou \textit{bound consistency}. Elles enlèvent moins de valeur mais l'étape de propagation est plus rapide. Les consistances plus fortes ont également été définies. Bien qu'elles soit plus coûteuses à atteindre, leur puissance d'élagage est particulièrement adaptée pour des problèmes combinatoires complexes tels que ceux figurant dans la vie réelle.
  
   
  Dans ce mémoire, pour la partie théorique, nous étudions les différents niveaux de consistance plus forte qui réduisent le domaine des variables pour les contraintes binaire et les contraintes non-binaires. Pour les contraintes binaires, nous abordons les différentes consistances tels que : \textit{Restricted Path Consistency (RPC), Path Inverse Consistency (PIC), Max Restricted Path consistency (MaxRPC), Neighborhood Inverse   Consistency (NIC), Singleton Arc Consistency (SAC)}. Ces consistances seront étendues pour les contraintes non-binaires. \textit{PIC} a été étendu à \textit{rPIC}, \textit{RPC} à \textit{RPWC}, et \textit{MaxRPC} à \textit{MaxRPWC}. Dans \cite{stergiou2008strong}, \textit{NIC} est étendu à \textit{rNIC}.
  
  Pour la partie pratique, les algorithmes de propagation pour les différentes consistances associées avec les contraintes non-binaires ont été étudiés et implémenté dans le solveur AbsCon. Plus particulièrement, nous avons implémenté les algorithmes pour MaxRPWC, rPIC, et RPWC. Les résultats expérimentaux montrent que ces consistances sont efficaces dans certaines classes de problèmes car elles peuvent élaguer plus que la consistance de domaine.
  
  Le reste de la thèse est structuré comme suit. Le chapitre 2 présente le contexte et les définitions nécessaires. Dans le chapitre 3, nous étudions les différentes consistances pour les contraintes binaires et non-binaires. Dans le chapitre 4, les algorithmes pour atteindre les consistances plus fortes pour les contraintes non-binaires seront présentés. Dans le chapitre 5, nous présentons la structure du solveur AbsCon et l'implémentation de ces algorithmes. Le chapitre 6 donne des résultats expérimentaux. Enfin, nous donnons la conclusion et le travail futur.
  